Load Balancing

Purpose

provide a unified view of the entire backend system to the end user
because the end user doesn't are which exact server handles their request
distribute the load (requests/data) equally across the other app/db servers

How to configure: https://docs.google.com/document/d/1DxQzLpu1XPe_mRWsewNWtKL6E4uwKHQhBp7GX6Sg7qI/edit#heading=h.fzwcs020kou5
Tutorial: https://avinetworks.com/what-is-load-balancing/
Elastic Load Balancer (ELB - AWS): https://aws.amazon.com/elasticloadbalancing/getting-started/

142.250.192.4

IPv4: 0-255 . 0-255 . 0-255 . 0-255

total number of possibilities: 2^8 * 2^8 * 2^8 * 2^8 = 2^32 ~ 4 billion

number of devices on the internet: 100 billion - 1 trillion

Static vs Dynamic IPs

IPv6: 128 bits

Number of possibilities: 2^128 ~ 256 billion billion billion billion

Q: Which server should a particular request be sent to?

To understand this, we first must understand how the data is distributed across the various servers.

Because otherwise, we will end up sending the requests to servers which don't contain the appropriate data (Sanjana's request get sent to a server which contains Ashok's data)

How to store the data?

Q: Can we store all the data on 1 server?

No. We got multiple laptops because we were running out of resources (disk space / CPU / ..)

Q: Should we split the data randomly?

How will we retrieve it?

The data storage has to follow some logic - that can be repeated.

We should be able to find out at any time, which data is stored in which server.

Data Sharding

Vertical Partitioning (Normalization)

why? Because you want to normalize it

Horizontal Partitioning

why?

improve indexing performance
support multi-tenancy (prevent data cross-communication between clients)

Vertical Partitioning (across servers)

why?

Migrate to microservice / separation of concerns

Horizontal Partitioning (across servers)

why?

All the data cannot fit on a single server

Sharding

Sharding is simply "Horizontal Partitioning across servers"

Sharding Key - sharding is always based on some value - sharding key

How to choose a good sharding key - we will see this in a later lecture

Sharding <=> Routing

It should not be the case that sharding following logic A, but routing follows logic B.

Why?

Because if that is the case - then the requests will end up on servers that don't contain the necessary data!

The logic / algorithm must be the same for both sharding & routing

Therefore, all we have to do is use a Routing Algorithm.

Sharding happens via Routing

Routing is the thing that happens - sharding is just a side effect of routing!

If we're routing based on user-id, then automatically the sharding will happen based on user-id

Because if Sanjana's requests are being routed to server A, then only server A will be able to the store Sanjana's data (because server B / C never received requests with Sanjana's data in the first place!)

We only decide (which request -> which server)

The moment we decide (which request -> which server),

we've also automatically decided (which data -> which server)

Routing Algorithms

Routing algorithm runs inside the Load Balancers.

It is how the LB decides which request goes to which server

How "Good" is your routing?

What characteristics should a good routing algorithm have?

Fast - computationally easy to decide which request goes to which server
Equal distribution - should divide the load (data & requests) equally across all servers
We should be able to freely add/remove servers

servers are unreliable, so they can crash, so the number of servers can decrease
we might need to scale out more, so we might add more servers, so the number of servers will increase

Minimal data movement - When the number of servers change, the data movement must be minimal
Routing should be deterministic without exchanging information

we've multiple load balancers
all the load balancers should always be "in-sync" - they should forward the same type of requests (say Sanjana's requests) to the same server because otherwise, Sanjana's data will be all over the place
They must not have to constantly communicate with each other to be "in-sync" - because constant communication for every request will be too much of an overhead

Round Robin

Send the next request to the next server.

Simple % based technique

server_list = ["10.11.6.12", "10.11.5.17", ...]

fn handle_request(request):

key = request.user_id

N = len(server_list)

server_id = key % N

server = server_list[server_id]

forward_request(request, server)

server_list = [A, B, C, D]

user_id = 0 .... 100

Initial Distribution

A 0 4 8 ...

B 1 5 9 ...

C 2 6 10 ...

D 3 7 11 ...

n = 4

Adding / Removing servers

let's say server B crashes.

A 0 3 6 9 ...

C 1 4 7 10 ...

D 2 5 8 11 ...

Since server B has crashed, and users (1, 5, 9, ..) were previously on server B, of course, their data has to be migrated (how? Son Pari)

However, other users' data should not have to be migrated needlessly because their servers are still working - there's no need to move their data!

Is that the case?

No! Pretty all the data gets shuffles around.

Similarly, when we add servers, once again, the value of N will change. The value of (user_id % N) will also change for pretty much everyone.

Pros

Fast, Equal Distribution, No need of syncing information

Cons

Lots of unnecessary data movement!

Bucketting

Assign the server -> user_id in ranges

A will get user_ids 0 ... 99

B will get user_ids 100 ... 199

C will get user_ids 200 ... 299

D will get user_ids 300 ... 399

total users = 400

Adding / Removing servers

if Server B crashes

A will get user_ids 0 ... 132

C will get user_ids 133 ... 265

D will get user_ids 266 ... 399

More users sign up

We cannot accommodate new users in existing servers - because we have already decided the buckets.

So it is impossible to add new users without first buying more servers

Pros

Equal data distribution

Fast

Cons

Too much data re-shuffling

Cannot even add users

Mapping Table

What if the LB maintains a Hashmap from user_id to server_id?

server_list = ["10.11.6.12", "10.11.5.17", ...]

mapping = {

sanjana: A

prem: B

bathula: A

pallavi: C

venkat: B

...

}

fn handle_request(request):

key = request.user_name

server = mapping[key]

forward_request(request, server)

Adding / Removing servers / users

Let's suppose server B crashes

fn handle_server_crash(crashed_server):

for user, server in mapping:

if server == crashed_server:

// assign a new server to this user

new_server = get_random_server()

mapping[user] = new_server

son_pari_please_migrate(user, crashed_server, new_server)

fn handle_new_user(user):

server = get_random_server()

mapping[user] = server

If we do this, will the data of people that were earlier on the crashed server get moved? Yes (that is desired)

For the users whose servers are still running, will their data get moved? No.

Pros

Equal data distribution, Fast, minimizes data movement

Cons

We will have to keep this mapping table in sync for all the LBs.

If different LBs have a different mapping table, then the requests will end up in random servers!

Keeping data in sync, always, with very low latency => extremely hard problem
IMPOSSIBLE !

Consistent Hashing

Pros

All of the above!

Fast
equal load distribution
freely add/remove servers
minimal data movement
no need for any sync between LBs

Cons

None!

break from 8.50 am - 9.00 am

Hash Function

fn add(a, b):

return a + b

Function is a "deterministic" mapping from inputs to outputs.

add(2, 3) => 5

no matter how many times I call a function, it will always give me the same result for the same input

state = 0

fn proc add(a, b):

state = b

return a + b + state

in this case, the function procedure (impute function) doesn't always return the same value - because it has side effects

Hash function is a "digest" function. Function that takes as input anything, but returns values within a fixed range.

fn hash_1(data):

return (sum of ascii values of chars of data) % 100

fn hash_2(data):

return (sum of squares ascii values of chars of data) % 799

fn hash_3(data):

return (multiply even and odd numbers in the data) % 1337

in this case, no matter what the data, the output will always be from 0 .. 99

Definitions and properties: https://en.wikipedia.org/wiki/Hash_function
Cryptographically secure (extra guarantees): https://en.wikipedia.org/wiki/Cryptographic_hash_function
Family of hashes: https://en.wikipedia.org/wiki/Universal_hashing

Hash Ring - output space of a given hash function

Placing Users & Servers on the Hash Ring

Consider 1 hash function hash_0 for hashing the users

Consider k hash functions hash_1 ... hash_k for hashing the servers
typical value of k is 32 or 64

These hash functions are set-up while the LB is being coded/configured.

All the LBs for a system will have the same set of hash functions in their code.

All these (k+1) hash functions have the same output space (say 0 ... 2^64 - 1)

https://en.wikipedia.org/wiki/K-independent_hashing

suppose our hash function outputs values in the range 0.. (2^64 - 1)

Given 1 billion users, and 1 million servers, what is the probability that two hashes collide?

This probability will be very close to 0.

Consistent Hashing Algorithm

For each server that we have, we will hash it using all the hash functions hash_1 .. hash_k and put the server on the ring..
Whenever a request arrives, we will hash the user_id using the hash_0 and place the user on the ring
The request will be forwarded to the first server on the ring which is in the clockwise direction

import bisect

def custom_hash(data, i):

h = sum(ord(c) ** i | 0xaff for c in data)

h *= 3

h >>= 1

return h % 10

def build_ring(servers, k):

ring = []

for server in servers:

for i in range(1, k+1): # 1..k

h = custom_hash(server, i)

print(f'adding {server} to spot {h}')

ring.append((h, server))

ring = sorted(ring)

print('final ring:', ring)

return ring

def route(user):

user_hash = custom_hash(user, 0)

# I now need to find the 1st server in the ring

# that is to the right of the user

index = bisect.bisect_right(ring, (user_hash, user))

index = index % len(ring) # wrap it around the ring

server_hash, server = ring[index]

print(f'{user} hashed to {user_hash}. Routing them to {server} at location {server_hash}')

return server

servers = [

'10.11.1.13',

'10.11.2.17',

'10.11.13.167',

'10.11.12.255',

'10.11.1.0',

]

ring = build_ring(servers, 3)

route('Vishal')

route('Sanjana')

route('Vishal')

route('Sanjana')

Is the algo deterministic? will Sanjana always go to server C (as long as Sanjana is alive, and server C is running, and not servers are added/removed)?

Yes!

Is the algo fast?

Yes! The ring is a sorted array, and to find the nearest server in the clockwise direction, you have to do a binary search (upperbound) for the user's hash.

O(log (Nk)) where N is the number of servers, and k is the number of server hashes

https://arpitbhayani.me/blogs/consistent-hashing/

Do the LBs have to share any data to be in sync?

No!

Each LB knows which servers are running (via health-check/heartbeat)
The code in each LB is the exact same
So, each LB will calculate the same hashes and the same ring
So, each LB will calculate the same server for any user

Is the data distribution even?